package me.shan.sort.merge;

import lombok.Getter;

import java.util.Arrays;
import java.util.Stack;

/**
 * 归并排序非递归版，自己实现入栈出栈
 * @author shan.guo
 */
public class MergeSortStack {

    /**
     * 模拟递归调用
     * @param left 左边界
     * @param right 右边界
     * @param stack 程序调用栈
     */
    private static void call(int left, int right, Stack<Frame> stack) {
        if (stack.size() >= 1024) {
            throw new StackOverflowError("函数栈溢出啦，最多支持1024个栈帧");
        }
        stack.push(new Frame(left, getMid(left, right), right));
    }

    private static void pcGoto(Frame frame, int loc) {
        frame.setPc(loc - 1);
    }

    private static void ret(Stack<Frame> stack) {
        stack.pop();
    }

    public static void sort(int[] array) {
        Stack<Frame> stack = new Stack<>();
        int left = 0;
        int right = array.length - 1;
        call(left, right, stack);
        while (!stack.isEmpty()) {
            Frame frame = stack.peek();
            /*
            pc指针的含义
            0 判断边界条件，left是否大于等于right，如果是，则表示当前帧已处理完，pc跳转到4
            1 排序左边
            2 排序右边
            3 合并结果
            4 弹出栈
             */
            switch (frame.getPc()) {
                case 0:
                    if (frame.getLeft() >= frame.getRight()) {
                        pcGoto(frame, 4);
                    }
                    break;
                case 1:
                    call(frame.getLeft(), frame.getMid(), stack);
                    break;
                case 2:
                    call(frame.getMid()+1, frame.getRight(), stack);
                    break;
                case 3:
                    merge(array, frame);
                    break;
                case 4:
                    ret(stack);
                default:
            }
            // pc ++
            frame.setPc(frame.getPc() + 1);
        }
    }

    private static void merge(int[] array, Frame frame) {
        int l = frame.getLeft(), m = frame.getMid(), r = frame.getRight();
        int[] temp = new int[r - l + 1];
        int i = l, j = m + 1, k = 0;
        while (i <= m && j <= r) {
            if (array[i] <= array[j]) {
                temp[k] = array[i];
                i++;
            } else {
                temp[k] = array[j];
                j++;
            }
            k++;
        }
        while (i <= m) {
            temp[k] = array[i];
            k++;
            i++;
        }
        while (j <= r) {
            temp[k] = array[j];
            k++;
            j++;
        }
        System.arraycopy(temp, 0, array, l, temp.length);
    }

    private static int getMid(int left, int right) {
        return left + ((right - left) >> 1);
    }

    public static void main(String[] args) {
        int[] array = {2, 4, 6, 1, 3, 5, 7, 3, 2, 8, 9, 1, 7, 3, 6, 0, 5, 2};
        int[] temp = new int[array.length];
        System.arraycopy(array, 0, temp, 0, temp.length);
        sort(array);
        System.out.println(Arrays.toString(array));
        Arrays.sort(temp);
        System.out.println(Arrays.toString(temp));
    }

}

@Getter
class Frame {

    /**
     * 程序计数器PC
     */
    private int pc;

    /**
     * 左边界
     */
    private final int left;

    /**
     * 中点
     */
    private final int mid;

    /**
     * 右边界
     */
    private final int right;

    public Frame(int left, int mid, int right) {
        this.pc = 0;
        this.left = left;
        this.mid = mid;
        this.right = right;
    }

    public void setPc(int pc) {
        this.pc = pc;
    }
}